import functools


class Solution(object):
    def maxProductPath(self, grid):
        @functools.cache
        def dfs(i, j):
            if grid[i][j] == 0:
                p_val, n_val, p_flag, n_flag = 0, 0, True, True
            else:
                if i == 0:
                    if j == 0:
                        if grid[i][j] > 0:
                            p_val, n_val, p_flag, n_flag = grid[i][j], 0, True, False
                        else:
                            p_val, n_val, p_flag, n_flag = 0, grid[i][j], False, True
                    else:
                        last_p_val, last_n_val, last_p_flag, last_n_flag = dfs(i, j - 1)
                        if grid[i][j] > 0:
                            p_val, n_val, p_flag, n_flag = last_p_val * grid[i][j], last_n_val * grid[i][
                                j], last_p_flag, last_n_flag
                        else:
                            p_val, n_val, p_flag, n_flag = last_n_val * grid[i][j], last_p_val * grid[i][
                                j], last_n_flag, last_p_flag
                else:
                    if j == 0:
                        last_p_val, last_n_val, last_p_flag, last_n_flag = dfs(i - 1, j)
                        if grid[i][j] > 0:
                            p_val, n_val, p_flag, n_flag = last_p_val * grid[i][j], last_n_val * grid[i][
                                j], last_p_flag, last_n_flag
                        else:
                            p_val, n_val, p_flag, n_flag = last_n_val * grid[i][j], last_p_val * grid[i][
                                j], last_n_flag, last_p_flag
                    else:
                        last_p_val1, last_n_val1, last_p_flag1, last_n_flag1 = dfs(i - 1, j)
                        last_p_val2, last_n_val2, last_p_flag2, last_n_flag2 = dfs(i, j - 1)
                        last_p_val = max(last_p_val1, last_p_val2)
                        last_n_val = min(last_n_val1, last_n_val2)
                        last_p_flag = last_p_flag1 or last_p_flag2
                        last_n_flag = last_n_flag1 or last_n_flag2
                        if grid[i][j] > 0:
                            p_val, n_val, p_flag, n_flag = last_p_val * grid[i][j], last_n_val * grid[i][
                                j], last_p_flag, last_n_flag
                        else:
                            p_val, n_val, p_flag, n_flag = last_n_val * grid[i][j], last_p_val * grid[i][
                                j], last_n_flag, last_p_flag
            return p_val, n_val, p_flag, n_flag
        p_val, _, p_flag, _ = dfs(len(grid) - 1, len(grid[0]) - 1)
        if p_flag:
            return p_val % (10 ** 9 + 7)
        else:
            return -1


data = Solution()
grid = [[1, -2, 1],
        [1, -2, 1],
        [3, -4, 1]]
print(data.maxProductPath(grid))
